0932. 漂亮数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 分治

1. 📝 题目描述

• leetcode

如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个 漂亮数组 ：

• nums 是由范围 [1, n] 的整数组成的一个排列。
• 对于每个 0 <= i < j < n，均不存在下标 k（i < k < j）使得 2 * nums[k] == nums[i] + nums[j]。

给你整数 n，返回长度为 n 的任一 漂亮数组。本题保证对于给定的 n 至少存在一个有效答案。

示例 1 ：

输入：n = 4
输出：[2,1,4,3]

示例 2 ：

输入：n = 5
输出：[3,1,2,5,4]

---

提示：

• 1 <= n <= 1000

2. 🎯 s.1 - 分治

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number} n
 * @return {number[]}
 */
var beautifulArray = function (n) {
  if (n === 1) return [1]

  const odd = beautifulArray(Math.ceil(n / 2))
  const even = beautifulArray(Math.floor(n / 2))

  return [...odd.map((x) => 2 * x - 1), ...even.map((x) => 2 * x)]
}

• 时间复杂度：$O(n\log n)$，递归深度 $O(\log n)$，每层处理 $O(n)$
• 空间复杂度：$O(n\log n)$，递归过程中创建的数组

算法思路：

• 如果数组 A 是漂亮数组，则 2A - 1（全为奇数）和 2A（全为偶数）也是漂亮数组
• 奇数集合和偶数集合之间不会形成等差关系（一奇一偶之和为奇数，不可能是某个元素的两倍）
• 递归构建：将 [1, n] 拆分为奇数部分和偶数部分，分别递归求解后合并